package com.itheima.algorithm.datastructure;

/**
 * 有序链表去重
 */
public class Leetcode82 {

	/**
	 * 递归实现
	 * @return
	 */
	public static ListNode deleteDuplicatesByRecursion(ListNode p){
		// 边界条件
		if(p ==null || p.next == null){
			return p;
		}
		if(p.value ==p.next.value){
			//找到重复,一直找下一个不重复的
			ListNode x = p.next.next;
			while (x!=null && x.value == p.value){
				x = x.next;
			}
			//循环结束, x就是与p取值不同的节点
			return deleteDuplicatesByRecursion(x);
		}else{
			// 更新后续
			p.next = deleteDuplicatesByRecursion(p.next);
			return p;
		}

	}

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        //哨兵链表
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2, p3;
        while ((p2 = p1.next) != null
				&& (p3 = p2.next) != null) {
            if (p2.value == p3.value) {
                while ((p3 = p3.next) != null && p3.value == p2.value) {

                }
                //p3 找到了不重复的值
                p1.next = p3.next;
            }else{
            	//各元素向后移动
                p1 = p1.next;
            }
        }
        return s.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1,2,3,3,4,4,5);
        System.out.println(head);
        System.out.println(deleteDuplicatesByRecursion(head));
    }
}
